package net.tp.algo.sort;

/**
 * User: Trung
 * Date: 4/27/13
 * Time: 12:46 PM
 */
public class StringRadixQuickSort {

    public static void sort(String[] data) {

        sort(data, 0, 0, data.length - 1);

    }

    private static void sort(String[] data, int pos, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        char pv = charAt(data[lo], pos);

        int lt = lo, gt = hi, i = lo;
        while (i <= gt) {
            char c = charAt(data[i], pos);
            if (c < pv) {
                swap(data, lt++, i++);
            }
            else if (c > pv) {
                swap(data, i, gt--);
            }
            else {
                i++;
            }
        }

        sort(data, pos, lo, lt-1);
        if (pv > 0) sort(data, pos+1, lt, gt);
        sort(data, pos, gt+1, hi);
    }

    private static char charAt(String text, int pos) {
        return pos < text.length() ? text.charAt(pos) : (char)0;
    }

    private static void swap(String[] data, int i, int j) {
        String tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }


}
